#include <stdio.h>
#include <stdlib.h>
#include "heap.h"

#define TAM_INI 10
#define DOS 2
#define CERO 0
#define UNO 1

struct heap_t{
	void** vector;
	size_t cantidad;
	size_t tamanio;
	cmp_func_t cmp;
};

static void swap (void** vector, int a, int b){
	void* temp = vector[a];
	vector[a] = vector[b];
	vector[b] = temp;
}

static bool redimensionar_heap(heap_t* heap, size_t tamanio){
		void** aux = realloc (heap->vector, sizeof(void*) * tamanio);
		if (aux == NULL) return false;
		heap->vector = aux;
		heap->tamanio = tamanio;
		return true;
}

heap_t *heap_crear(cmp_func_t cmp){
	heap_t* heap = malloc(sizeof(heap_t));
	if(heap == NULL) return NULL;
	heap->vector = malloc(TAM_INI * sizeof(void*));
	if(heap->vector == NULL){
		free(heap);
		return NULL;
	}
	heap->cantidad = CERO;
	heap->tamanio = TAM_INI;
	heap->cmp = cmp;
	return heap;
}

bool heap_destruir(heap_t *heap, void destruir_elemento(void *e)){
	if(heap==NULL)return false;
	if(destruir_elemento != NULL){
			int i;
			for(i=CERO; i < heap->cantidad; i++){
					destruir_elemento(heap->vector[i]);
			}
	}
	free(heap->vector);
	free(heap);
	return true;
}

size_t heap_cantidad(const heap_t *heap){
	return heap->cantidad;
}

bool heap_esta_vacio(const heap_t *heap){
	return (heap->cantidad == CERO);
}

void *heap_ver_max(const heap_t *heap){
	if(heap_esta_vacio(heap)) return NULL;
	return heap->vector[CERO];
}

static void upheap(void** vector,size_t pos,size_t cant,cmp_func_t cmp){
	if(pos > CERO){
		int padre = (pos-UNO)/DOS;
		int r = cmp(vector[padre],vector[pos]);
		if (r < CERO){
				swap(vector,padre,pos);
				upheap(vector,padre,cant,cmp);
		}
	}
}
static void downheap(void** vector,size_t pos,size_t cant,cmp_func_t cmp){
	int hizq = (DOS*pos) + UNO;
	int hder = (DOS*pos) + DOS;
	if(hizq >= cant){
			return; // Es una hoja
	}	             
	if(hizq == (cant - UNO)){  // Tiene un solo hijo
			int r = cmp(vector[pos],vector[hizq]);
			if(r<CERO) swap(vector,pos,hizq);
			return;
	} // Dos hijos
	int max;                            
	int r = cmp(vector[hizq],vector[hder]);
	if(r>CERO) max = hizq;
	else max = hder;
	r = cmp(vector[pos],vector[max]);
	if(r<CERO){
		swap(vector,pos,max);
		downheap(vector,max,cant,cmp);
	}
	return;
}



bool heap_encolar(heap_t *heap, void *elem){
	if(heap->cantidad == heap->tamanio){
		if(!redimensionar_heap(heap,heap->tamanio*DOS)) return false;
	}
	heap->vector[heap->cantidad] = elem;
	heap->cantidad ++;
	upheap(heap->vector,(heap->cantidad - UNO),heap->cantidad,heap->cmp);
	return true;
}

void *heap_desencolar(heap_t *heap){
	if(heap_esta_vacio(heap)) return NULL;
	void* dato_borrado = heap->vector[CERO];
	heap->vector[CERO] = heap->vector[(heap->cantidad-UNO)];
	heap->cantidad --;
	downheap(heap->vector,CERO,heap->cantidad,heap->cmp);
	if((heap->cantidad <= (heap->tamanio/4)) && (heap->tamanio > TAM_INI)){
		redimensionar_heap(heap,heap->tamanio/2);
	}
	return dato_borrado;
}

static void heapify(void **elementos, size_t cant, cmp_func_t cmp){
	int padre_ult = (cant - DOS) / DOS;
	int i;
	for(i=padre_ult;i>=CERO;i--){
		downheap(elementos,i,cant,cmp);
	}
}

void heapsort(void **elementos, size_t cant, cmp_func_t cmp){
	if (cant==0) return;
	heapify(elementos,cant,cmp);
	int i;
	for(i=cant-UNO;i>0;i--){
		swap(elementos,CERO,i);
		downheap(elementos,CERO,i,cmp);	
	}
}
